Disk caching is a known disk access avoidance technique that maintains a set of data blocks in a high speed disk cache memory, with the expectation that some or all of these data blocks will subsequently be requested (demanded) by a data processor. In addition to demanded data blocks that are cached during each disk access, a read-ahead disk cache determines a number of additional blocks to be fetched into the disk cache, and thus eliminates the need of some future disk access to the data. In that a disk access, also known as an Input/Output (I/O) Process, is typically one or more orders of magnitude slower than an access to the semiconductor memory that comprises the disk cache, it can be appreciated that the maintenance of prefetched data units in the disk cache yields significant improvements in processing efficiency.
The number of data units to be prefetched, that is, the prefetch length (L), may be assigned statically or may be dynamically adjusted in some fashion based on disk access patterns. However, the conventional read-ahead disk cache only accesses, using a single I/O Process, data blocks or units, for example sectors, that are physically consecutive to the demanded data blocks. Since a sequentially accessed file may not have physical sequentiality on the disk, i.e. the data may not reside in consecutive data blocks, the performance advantage of the read-ahead disk cache is reduced. Furthermore, in known types of conventional disk cache designs, a read-ahead is issued only when the demanded data is not located within the disk cache, i.e., during disk cache misses. No file access process is issued for a disk cache hit condition.
FIG. 2a illustrates the logical organization of a plurality of sequential data blocks (B) on a mass storage device, typically a disk. By example, each data block may represent a sector or a track of the disk. The group of data blocks are associated with a file. By example only, the file may contain employee records for an organization. In response to a Demand for a Block (B.sub.i), the Block B.sub.i is Fetched, and the blocks B.sub.i+1 to B.sub.i+3 are Prefetched. FIG. 2b illustrates a physical, as opposed to a logical, organization of the data Blocks. As can be seen, the Blocks associated with the file may not be physically contiguous to one another, but may instead be separated by some number of Blocks (designated with an X) that are associated with another file, or that are defective and, hence, unused. The conventional disk cache mechanism performs one I/O Process to access the Demand Block B.sub.i and also the Prefetched Blocks B.sub.i+1 to B.sub.i+3. Because of disk latencies and/or other disk access characteristics, a significant amount of time may elapse between the access to Blocks (B.sub.i and B.sub.i+1) and the Blocks (B.sub.i+2 and B.sub.i+3). As a result, the Demanded Block (B.sub.i) may not be returned to the requester for a significant period of time, thereby reducing the efficiency of the disk cache.
It is thus one object of this invention to provide a method to improve the efficiency of a data cache, particularly a disk cache.
It is another object of this invention to provide a disk cache having a prefetch mechanism that is optimized for efficiently responding to sequential Demands for data units.